package org.example.SolutionNew001;

import java.util.Stack;

public class DoublePoint04 {
    public static void main(String[] args) {
        DoublePoint04 sol = new DoublePoint04();
        int[] height=new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(sol.trap(height));

    }

    //接雨水必须掌握的思路：前瞻后顾，短板效应,动态规划
    public int trap1(int[] height) {
        int n=height.length;
        int[] lmax=new int[n];
        int[] rmax=new int[n];

        lmax[0]=height[0];
        rmax[n-1]=height[n-1];

        //第一遍循环，找左侧的最大值
        for(int i=1;i<n;i++){
            lmax[i]= Math.max(height[i],lmax[i-1]);
        }

        //第二遍循环，找右侧最大
        for(int i=n-2;i>=0;i--){
            rmax[i]= Math.max(height[i],rmax[i+1]);
        }

        //第三遍循环，找短板效应下能接的最大雨水值
        int res=0;
        for(int i=0;i<n;i++){
            res+=Math.min(lmax[i],rmax[i])-height[i];
        }
        return res;
    }

    public int trap2(int[] height) {
        int n= height.length;
        Stack<Integer> stack=new Stack<>();
        int res=0;
        for(int i=0;i<n;i++){
            while(!stack.isEmpty()&&height[i]>height[stack.peek()]){
                int top=stack.pop();
                if(stack.isEmpty()) break;
                int left=stack.peek();
                int curLength=i-left-1;
                int curheight=Math.min(height[left],height[i])-height[top];
                res+=curLength*curheight;
            }
            stack.push(i);
        }
        return res;
    }

    public int trap(int[] height) {
        int res=0;
        int n=height.length;
        int left=0,right=n-1;
        int lM=0,rM=0;
        while(left<right){
            lM=Math.max(height[left],lM);
            rM=Math.max(height[right],rM);
            if(height[left]<height[right]){
                res+=lM-height[left];
                left++;
            }else{
                res+=rM-height[right];
                right--;
            }
        }
        return res;
    }
}
